#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass)
    {
        std::vector<std::vector<double>> dp(query_row + 1, std::vector<double>(100, 0.0));
        dp[0][0] = poured;

        for (int i = 0; i < query_row; ++i)
        {
            for (int j = 0; j <= i; ++j)
            {
                if (dp[i][j] > 1)
                {
                    dp[i + 1][j] += (dp[i][j] - 1) / 2;
                    dp[i + 1][j + 1] += (dp[i][j] - 1) / 2;
                }
            }
        }

        return dp[query_row][query_glass] >= 1.0 ? 1.0 : dp[query_row][query_glass];
    }
};